#!/Users/timmenzies/opt/gawk/bin/gawk -f 
 
# where2.awk
# Revision: 296
# Built by timmenzies on Fri Jul 29 20:43:58 PDT 2011.

#   _ _ _                                               ((
#  |=|=|=|.----------------------------------------.    _))_
#  |-|-|-|| AWK code of a tiny book on data mining | ___\__/)_
#  |_|_|_|'----------------------------------------| |_|_~~_|_|

# This file is part of TINY.
#
# TINY is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# TINY is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
#  along with TINY.  If not, see <http://www.gnu.org/licenses/>.

 @include "lib.awk"

#Globals
#=======

#== C ==

#Cluster id

#== A ==

#Number of attribtes

#== K == 

#Class attribute id

#== R ==

#Number of rows.

#Parser
#======

 BEGIN        { TooSmall=20; Pinch = 10^-6; 	CONVFMT = "%.10f"; Missing="?"}
  /@attribute/ { Name[++A]=$2; 
                if ($3 ~ /(numeric|integer|real|float)/) { Num[A] } else { Sym[A] }
              }
 /@data/      { FS=","; C=0
                K = K<0 ? K = A + 1  + K : K; 
                next }
 /@/          { next }
              { gsub(/%.*/,""); gsub(/[ \t]*/,""); if (/^$/) next }
 NF==A        { cells(C,initRow()) }
 END          { divide(0) }

##### storage

 BEGIN{_R=0}
 function initRow(    col) {
 	_R++
     for(col=1;col<=A;col++) Data[_R, col] = $col
 	return _R
 } # end _R
 function cells(c,row,      col,val) {
 	Has[c][row] 
 	for(col in Num) 
 		if ((val=Data[row,col]) != Missing) 
 			numCell(c,row,col,val)
 	for(col in Sym) 
 		if ((val=Data[row,col]) != Missing) 
 			symCell(c,row,col,val)
 }
 function numCell(c,row,col,val) {
 	N[c,col]++
 	Sum[c,col] += val
 	SumSq[c,col] += val * val
 	Value[c,col][row]=val	
 }
 function symCell(c,row,col,val) {
 	Value[c,col][val]++
 	Values[c,col]++
 }
#### splitter
 function split_on(c,   col,tmp,max,out) {
 	for(col in Num) if (col != K) tmp[col] = sd( SumSq[c,col],Sum[c,col],N[c,col]) 
 	for(col in Sym) if (col != K) tmp[col] = ent(Value[c,col],Values[c,col]) 
 	for(col in Num) if (col != K) tmp[col] = norm_sd(  tmp[col])
 	for(col in Sym) if (col != K) tmp[col] = norm_ent( tmp[col])
 	for(col in tmp) if (tmp[col] > max) { max= tmp[col]; out=col}
 	return out
 }
 function divide(c,  left,right,div,  kids,kid,action) {
 	if  (length(Has[c]) <= TooSmall) return Dead[c]=1
 	Split[c] = div = split_on(c)
 	if (div in Num)
           divideNum(c,Split[c],kids, Has[c], Value[c,div])
     else  divideSym(c,Split[c],kids, Has[c], Value[c,div])
 	for(kid in kids)
 		divide(kids[kid])
 }
 function divideNum(c,div,kids,rows,values,   all,n,median,row) {
 	n = asort(values,all)	
 	Splitter[c] = median = all[int(n/2)]
 	kids[1] = newC(c,0)
 	kids[2] = newC(c,median)
 	for(row in rows) 
 		Data[row,div] <= median ? cells(kids[1],row) : cells(kids[2],row)
 }	
 function divideSym(c,div,kids,rows,values,    val,row) {
 	for(val in values) kids[val] = newC(c,val)
 	for(row in rows)   cells(kids[Data[row,div]],row)	
 }
 function newC(c,val) {
 	C++
 	Parent[C] = c 
 	Child[c][val] = C
 	return C
 }
#### tree print
 function cprint(c,pre,pad,             op, vals,val) {
 	if (! (c in Split)) return 0
 	print pad c ":" Name[Split[c]] " (" length(Has[c]) ")"
 	op = Split[c] in Num ? ">=" : "="
 	if(length(Child[c]))
 		for(val in Child[c]) 
 			cprint(Child[c][val],op val, pad "  ")
 }
 #### diversity measures
 BEGIN {_Minsd= 10^31; _MaxSd = -1*_MinSd
        _MinE= 10^31;   _MaxE = -1*_MinE}

 function norm_ent(s) { return norm(s,_MinE ,_MaxE)  }
 function norm_sd(s){ return norm(s,_MinSd,_MaxSd) }

 function sd(sumSq,sumX,n,tmp) {
     tmp = sqrt((sumSq-((sumX*sumX)/n))/(n-1));
 	if (tmp < _Minsd) _Minsd = tmp
 	if (tmp > _Maxsd) _Maxsd = tmp
 	return tmp
 }
 function ent(a,n,      i,p,tmp) {
 	for(i in a)  
 		if (a[i] > TooSmall) {
 			p = a[i]/n 
 		    tmp += -1*p*log(p)/log(2)
 	}
 	if (tmp < _MinE) _MinE = tmp
 	if (tmp > _MaxE) _MaxE = tmp
 	return tmp
 } # end _Minsd  _Maxsd _MinE MaxE

